% !TeX spellcheck = de_DE
\documentclass[UTF8,a4paper]{book} %设为A4纸
\usepackage{geometry}
\geometry{left=2cm,right=3cm,top=4cm,bottom=3cm} %设置页边距
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{verbatim}  %use verbatim
\usepackage{ctex}
\usepackage{ifthen}
\usepackage{makeidx}

\usepackage{xcolor}
\colorlet{lightcyan}{cyan!40!white}

%\usepackage{chngcntr}
\usepackage{stackengine}

\usepackage{tasks}

\newlength{\longestlabel}

\settowidth{\longestlabel}{\bfseries viii.}

\usepackage[lastexercise]{exercise}
%\counterwithin{Exercise}{chapter}
%\counterwithin{Answer}{chapter}

%\renewcounter{Exercise}[chapter]

\setlength{\QuestionIndent}{7em}

\usepackage{enumerate}

\newboolean{printanswer}

%---------------------答案格式开始定义-----------------------------------------
%判断题后面加括号
\newcommand{\pd}[2][1]{\nolinebreak\dotfill\mbox{\raisebox{-1.8pt}
		{$\cdots$}(\makebox[#1 cm][c]{
			\ifthenelse{\boolean{printanswer}}
			{\ifthenelse{\equal{#2}{t}}{\Checkmark}{\XSolid}}
			{}
		})}}


%填空题画线  \tk
%\newcommand{\tk}[2][2.5]{\; \underline{\hspace{#1 cm} \hphantom{#2} \hspace{#1 cm} } \, }
\usepackage{ulem}
\newcommand{\tk}[2][0.5]{\;\uline{ 
		\hspace*{#1 cm}
		\ifthenelse{\boolean{printanswer}}{#2}{\hphantom{#2}}  
		\hspace*{#1 cm}
} }
%简答题  \jd
\newcommand{\jd}[2][4]{\par
	%\begin{minipage}[t][#1cm][t]{0.92\linewidth}	
		\ifthenelse{\boolean{printanswer}}{
			\begin{Answer}
				答：\par
				#2
			\end{Answer}
		}
		{}  
	%\end{minipage} 
}	
%---------------------------答案格式结束定义---------------------------------
\usepackage[breaklinks,colorlinks,linkcolor=black,citecolor=black,urlcolor=black]{hyperref} %生成pdf中的书签
\setboolean{printanswer}{true} %控制是否输出习题的答案

\begin{document}
	
	
    \chapter{预备知识}
	\section{集合}
	    \begin{Exercise}
	       设
	       $A=\left \lbrace a,\left \lbrace a\right \rbrace  \right\rbrace $
	       ,下列各式成立吗？写出判断过程。\par
	       $\left\lbrace a \right\rbrace  \in \rho(A);\left\lbrace a\right\rbrace  \subseteq \rho (A);\left\lbrace \left\lbrace a\right\rbrace \right\rbrace  \in \rho (A);\left\lbrace \left\lbrace a\right\rbrace \right\rbrace  \subset \rho(A)$
	    \end{Exercise}
	   	\jd{
	   			先计算幂集，然后判断幂集和各个各部分的关系。
	   	}

	   	\begin{Exercise}
	   		全集$E=\{1,2,3,4,5\},A=\{1,4\},B=\{1,2,5\},C=\{2,4\}$,计算：\par
	   		\begin{enumerate}[1)]
	   			\item  $A \cap \sim B$
	   			\item $(A \cup B) \cap (A \cup C)$
	   			\item $\sim (A \cup B)$
	   			\item $\rho(A)-\rho(C)$
	   		\end{enumerate}
	   	\end{Exercise}
   		\jd{
   			$\sim B =\{3,4 \},\rho(A)=\{\phi,\{1,4\},\{1\},\{4\} \},\rho(C)=\{\phi,\{2,4\},\{2\},\{4\} \}$\par
   			\begin{enumerate}[1)]
   				\item  $A \cap \sim B=\{4\}$
   				\item $(A \cup B) \cap (A \cup C)=\{1,2,4\}$
   				\item $\sim (A \cup B)=\{3\}$
   				\item $\rho(A)-\rho(C)=\{\{1,4\},\{1\}\}$
   			\end{enumerate}
   		}
	   	\begin{Exercise}
	   		A,B,C是任意三个集合，证明$A\oplus (B \oplus C) =(A \oplus B) \oplus C.$
	   	\end{Exercise}
   		\jd{先按照对称差的定义，用基本运算来表示，然后在组合为右边形式。}
   	\section{关系}
	   	\begin{Exercise}
	   		集合$A=\left\lbrace 16,17,18,19\right\rbrace $,R为A上的关系$R=\left\lbrace <16,17>,<17,18>,<18,19>\right\rbrace $，请问R的逆关系存在吗？如果存在请写出来。
	   	\end{Exercise}
   		\jd{这道题来源于16级的学生做17级的班助，17级的做18级的，18级做19级的这种关系，二元逆关系总是存在的，将所有序偶倒着写就是二元逆关系。}
	   \begin{Exercise}
	   	$\mathbb{Z}$为整数集合，请问此集合上的相等关系是等价关系吗？如果是请证明。
	   \end{Exercise}
   		\jd{首先要知道什么是等价关系：自反，传递，对称，很容易验证整数集上的相等关系符合等价定义。}
		\begin{Exercise}
			请证明笛卡尔积不满足结合律。
		\end{Exercise}
		\jd{
			证明不满足，其实只需要给出一个反例即可，设$A=\{1\},B=\{a,b\},C=\{x,y\}$，$(A\times B )\times C=\{<<1,a>,x>,<<1,a>,y>,<<1,b>,x>,<<1,b>,y>\},A\times (B \times C)=\{<1,<a,x>>,<1,<a,y>>,<1,<b,x>>,<1,<b,y>>\}$,显然这两个集合是不相等的。
		}
	\section{函数}
		\begin{Exercise}
			$\mathbb{R}$为实数集合，二维向量定义为$V_2 =\left\lbrace (x,y) \mid x \in \mathbb{R},y \in \mathbb{R}\right\rbrace $，矩阵$C=\begin{vmatrix}
			0 & 1 \\ 
			1 & 0
			\end{vmatrix} $,定义矩阵与二维向量的乘运算$A\cdot v_2=\begin{vmatrix}
			a & b \\ 
			c & d
			\end{vmatrix} \cdot (x,y)=(a\times x+b \times y,c\times x+ d\times y )$,请问$C \cdot v,v \in V_2$是从$V_2$到$V_2$的一个函数吗？并说明理由。
		\end{Exercise}
		\jd{
			判断关系是不是一个函数，就要看是否每个x是否有唯一的y对应，显然这是符合定义的。
		}
		\begin{Exercise}
			请分别给出实数域上的满射函数、单射函数、双射函数的例子，并说出原因。
		\end{Exercise}
		\jd{满射就是值域中所有的元素都有一个像对应，单射是定义域中没有两个不同的元素像相同，双射就是既是满射又是单射。}
		%\noindent\rule{\paperwidth}{1.5pt}
\chapter{整除}
	\begin{Exercise}
		证明，若$2 \mid n,5 \mid n,7\mid n$，那么$70 \mid n$.
	\end{Exercise}
	\jd{
		$2 \mid n,5 \mid n,7\mid n \Rightarrow lcm(2,5,7) \mid  m \Rightarrow 70 \mid  n$
	}
	\begin{Exercise}
		证明任意三个连续的正整数的乘积都被6整除。
	\end{Exercise}
	\jd{
		$m(m+1)(m+2)$\par
		$m=1,1 \times 2 \times 3 = 6$,成立。\par
		设m=k也成立。\par
		$m=k+1,(k+1)(k+2)(k+3)=(k+1)(k+2)k+3(k+1)(k+2)$，可见式子的第一部分可被6整除，要想证明$3(k+1)(k+2)$可被6整除，可证明$(k+1)(k+2)$可被2整除,不管k是奇数还是偶数，两个成绩项一定有个偶数项，所以可以被2整除。
	}
	\begin{Exercise}
		证明每个奇数的平方都具有8k+1的形式。
	\end{Exercise}
	\jd{
		奇数可以写为$2k+1$,奇数的平凡是$(2k+1)^2 = 4k^2+4k+1=4k(k+1)+1$,可知$k(k+1)$是偶数，所以可以写成2m的形式，$4k(k+1)+1$可以写成$8m+1$形式。
	}
	\begin{Exercise}
		求如下整数对的最大公因子，并写出求解过程。\par
		(1)(55,85) \hspace{1cm}  (2)(202,282) \hspace{1cm} (3)(666,1414) \hspace{1cm} (4)(20785,44350)
	\end{Exercise}
	\jd{$gcd(55,85)=5,gcd(55,85)=2,gcd(666,1414)=2,gcd(20785,44350)=5$，下面给出第一对数的实际计算过程：\par
		$
		85=55 \times 1 + 30\\
		55=30 \times 1 +25\\
		30=25 \times 1 +5\\
		25=5 \times 5\\
		gcd(55,85)=5
		$
	}
	\begin{Exercise}
		求如下整数对的最小公倍数，并写出求解过程。\par
		(1)(231,732) \hspace{1cm}  (2)(-871,728) 
	\end{Exercise}
	\jd{
		先求$gcd(231,732),lcm(231,732)=(231 \times 732) \div gcd(231,732)$，计算结果如下：\\
		$lcm(231,732)=56364,lcm(-871,728)=48776 $
	}
	\begin{Exercise}
		求以下整数的标准分解式，并写出求解过程。\par
		(1)36 \hspace{1cm}(2)69 \hspace{1cm}(3)200 \hspace{1cm}(4)289 \hspace{1cm}
	\end{Exercise}
	\jd{
		利用小于次数的素数去依次除次数，可以整除，则找到一个素因子，依次可以找到所有素因子。分解结果如下(sagemath factor)：\\
		$36=2^2 * 3^2,69=3*23,200=2^3 * 5^2,289=17^2$
	}
	\begin{Exercise}
		求以下整数的标准分解式，并写出求解过程。\par
		(1)625 \hspace{1cm}(2)2154 \hspace{1cm}(3)2838 \hspace{1cm}(4)3288 \hspace{1cm}
	\end{Exercise}
	\jd{
		利用小于次数的素数去依次除次数，可以整除，则找到一个素因子，依次可以找到所有素因子。分解结果如下:\par
		$625=5^4,2154=2 * 3 * 359,2838=2 * 3 * 11 * 43,3288=2^3 * 3 * 137$
	}
\chapter{同余}
	\begin{Exercise}\label{exer:43}
		设模m=16,求解1,9,16,17,25,160模16余数,并找出同余的数来。
	\end{Exercise}
	\jd{
		依次计算上面各数模16的余数，余数分别为1、9、0、1、9、0,根据同余定义，我们有$1 \equiv 17 (mod \ 16),9 \equiv 25 (mod \ 26),16 \equiv 160 (mod \ 26)$。
	}
	\begin{Exercise}
		求$7^{2046}$写成十进制数时的个位数。
	\end{Exercise}
	\jd{答案是：9,计算过程如下：\par
		$7^2=49\equiv 9(mod  10), 9^2 =81 \equiv 1(mod  10),2046=4 \times 511+2 \Rightarrow 7^{2046} \equiv ((7^2)^2)^{511} \times 7^2 \equiv 9 (mod  10)$
	}
	\begin{Exercise}
		求$2^{1000}$的十进制表示中的末尾两位数字。
	\end{Exercise}
	\jd{答案为：76，计算过程如下：\par
		$
		2^ 0 = 1 (mod 100),
		2^ 1 = 2 (mod 100),
		\uwave{2^ 2 = 4 (mod 100)},
		2^ 3 = 8 (mod 100),
		2^ 4 = 16 (mod 100)\\
		2^ 5 = 32 (mod 100),
		2^ 6 = 64 (mod 100),
		2^ 7 = 28 (mod 100),
		2^ 8 = 56 (mod 100),
		2^ 9 = 12 (mod 100)\\
		2^ {10} = 24 (mod 100),
		2^ {11} = 48 (mod 100),
		2^ {12} = 96 (mod 100),
		2^ {13} = 92 (mod 100),
		2^ {14} = 84 (mod 100)\\
		2^ {15} = 68 (mod 100),
		2^ {16} = 36 (mod 100),
		2^ {17} = 72 (mod 100),
		2^ {18} = 44 (mod 100),
		2^ {19} = 88 (mod 100)\\
		2^ {20} = 76 (mod 100),
		2^ {21} = 52 (mod 100),
		\uwave{2^ {22} = 4 (mod 100)},
		2^ {23} = 8 (mod 100),
		2^ {24} = 16 (mod 100)\\
		2^ {25} = 32 (mod 100),
		2^ {26} = 64 (mod 100),
		2^ {27} = 28 (mod 100),
		2^ {28} = 56 (mod 100),
		2^ {29} = 12 (mod 100)\\
		2^ {30} = 24 (mod 100),
		2^ {31} = 48 (mod 100),
		2^ {32} = 96 (mod 100),
		2^ {33} = 92 (mod 100),
		2^ {34} = 84 (mod 100)\\
		2^ {35} = 68 (mod 100),
		2^ {36} = 36 (mod 100),
		2^ {37} = 72 (mod 100),
		2^ {38} = 44 (mod 100),
		2^ {39} = 88 (mod 100)\\
		$
		$1000=20\times 50 \Rightarrow 2^{1000}={2^{20}}^50 \equiv 2^{20} \equiv 76 (mod\ 100)$
	}
	\begin{Exercise}
		已知2019年9月29日是星期天，问之后的$2^{100}$天是星期几？第$2^{200}$天呢？
	\end{Exercise}
	\jd{
		由于$2^1 \equiv 2(mod\ 7),2^2 \equiv 4 (mod\ 7),2^3 \equiv 1(mod\ 7)$\par
		所以$2^{3\times 33} \equiv 1 (mod\ 7)$\par
		又因为$100=3 \times 33 +1$,所以$2^{100}=2^{3 \times 33 +1}=2^{3\times 33} \times 2 \equiv 2 (mod\ 7)$，所以第$2^{100}$天是星期三。
		同理$200=3\times 66+2$,$2^{200}=2^{3 \times 66 +2}=2^{3\times 66} \times 2^2 \equiv 4 (mod\ 7)$,所以第$2^{200}$天是星期五.
	}
	\begin{Exercise}
		求$1^5 +2^5 +3^5 + \ldots + 99^5$之和被4除的余数。
	\end{Exercise}
	\jd{
		$4^5+5^5+6^5+7^5 \equiv 0+1^5+2^5+3^5 (mod  4)\\
		\ldots \\
		96^5+97^5+98^+99^5 \equiv 0+1^5+2^5+3^5 (mond  4)$共有24组，$24 \times (1+32+3^5) \equiv 0 (mod  4)$
	}
	\begin{Exercise}
		写出模9的一个完全剩余系，它的每个数都是奇数。
	\end{Exercise}
	\jd{
		$\left\lbrace 0,1,2,3,4,5,6,7,8\right\rbrace ,2k+1,\left\lbrace 1,3,5,7,9,11,13,15,17\right\rbrace $
	}

	\begin{Exercise}
		写出模9的一个完全剩余系，它的每个数都是偶数。
	\end{Exercise}
	\jd{
		$\left\lbrace 0,1,2,3,4,5,6,7,8\right\rbrace ,2k,\left\lbrace 0,2,4,6,8,10,12,14,16\right\rbrace $
	}

	\begin{Exercise}
		用模5和模6的完全剩余系，表示模30的完全剩余系。
	\end{Exercise}
	
	\jd{
		模5的完全剩余系
		$\left\lbrace 0,1,2,3,4 \right\rbrace $\par
		模6的完全剩余系$\left\lbrace 0,1,2,3,4,5 \right\rbrace $\par
		5，6互质,$30=5 \times 6$\par
		$
		m_i \times 5 + n_j \times 6,\left\lbrace 
		0,1,2,3,4,5,
		11,17,23,29,35,
		10,16,22,28,34,40,
		15,21,27,31,39,45,
		20,26,32,38,44,50 \right\rbrace 
		$
	}
	
	\begin{Exercise}
		写出12的最小正缩系。
	\end{Exercise}
	\jd{
		最小正完全系\{ 1,2,3,4,5,6,7,8,9,10,11,12 \},与12互素的有\{1,5,7,11\}
	}
	\begin{Exercise}
		用模5和模6的缩系，表示模30的缩系。
	\end{Exercise}
	\jd{
		5和6互素,x和y遍历5和6的缩系，$5x+6y$也遍历模$5 \times 6$的缩系。模5的缩系$\left\lbrace 1,2,3,4 \right\rbrace $，模6的缩系$\left\lbrace 1,5 \right\rbrace $，模30的缩系$
		11,16,21,30,
		35,40,45,50
		$
	}
	\begin{Exercise}
		计算以下整数的欧拉函数。\par
		(1)24 \hspace{1cm}(2)64 \hspace{1cm}(3)187 \hspace{1cm}(4)360 \hspace{1cm}
	\end{Exercise}
	\begin{Exercise}
		计算$8 \times 9 \times 10 \times 11 \times 12 \times 13 (mod \  7)$.
	\end{Exercise}
	\jd{
			$\because 8 \equiv 1 (mod \ 7)\\
			9 \equiv 2 (mod \ 7)\\
			10 \equiv 3 (mod \ 7)\\
			11 \equiv 4 (mod \ 7)\\
			12 \equiv 5 (mod \ 7)\\
			13 \equiv 6 (mod \ 7)\\
			\therefore 720 \equiv 6 (mod \ 7)\\
			$
	}

	\begin{Exercise}
		求$229^{-1}(mod \ 281)$
	\end{Exercise}
	\jd{
		229模281逆元是27.\\
		具体解法是首先判断$gcd(229,281)=1$，逆元存在，然后利用扩展欧几里得算法求逆元$s_i=s_{i-2}+q_{i-1}s_{i-1},t_i=t_{i-2}+q_{i-1}t_{i-1}$：\\
		\begin{tabular}{|c|c|c|c|c|}
			\hline 
			i& $r_i$ & $q_i$ & $s_i$ & $t_i$ \\ 
			\hline 
			0& 281 & - & 1 & 0 \\ 
			\hline 
			1& 229 & 1 & 0 & 1 \\ 
			\hline 
			2& 52 & 4 & 1 & -1 \\ 
			\hline 
			3& 21 & 2 & -4 & 5 \\ 
			\hline
			4& 10 & 2 & 9 & -11 \\ 
			\hline
			5& 1 & 10 & -22 & 27 \\ 
			\hline
			5& 0 & - & - & - \\ 
			\hline
		\end{tabular} 
		
%		我们先用sagemath直接求解一下：\\
%		$\begin{verbatim}
%			sage: 229.inverse_mod(281)
%			27
%			sage:
%		\end{verbatim}$
	}
	
	\begin{Exercise}
		求$3169^{-1} (mod\ 3571)$.
	\end{Exercise}
	\jd{
		利用欧几里得扩展算法计算，计算结果为：2887.\\
		sagemath验证语句：3169.inverse\_mod(3571)
	}

	\begin{Exercise}
		解方程$105x+121y=1(x,y \in \mathbb{Z})$.
	\end{Exercise}
	\jd{根据欧几里得扩展算法，我们有$gcd(r_0,r_1)=s_nr_0+t_nr_1$，我们设$r_0=121,r_1=105$,同时我们可知105与121互素($gcd(121,105)=1$)，可见欧几里得扩展算法最后的等式为$121s_n+105t_n=1$，与所求的方程相同，我们利用扩展欧几里得算法进行计算：\par
		\begin{tabular}{|c|c|c|c|c|}
			\hline 
			& $r_i$ & $q_i$ & $s_i$ & $t_i$ \\ 
			\hline 
			0& 121 & - & 1 & 0 \\ 
			\hline 
			1& 105 & 1 & 0 & 1 \\ 
			\hline 
			2& 16 & 6 & 1 & -1 \\ 
			\hline 
			3& 9 & 1 & -6 & 7 \\ 
			\hline 
			4& 7 & 1 & 7 & -8 \\ 
			\hline 
			5& 2 & 3 & -13 & 15 \\ 
			\hline 
			6& 1 & 2 & 46 & -53 \\ 
			\hline 
			7& 0 &  &  &  \\ 
			\hline 
		\end{tabular} 
	}
	\begin{Exercise}
		求解一次同余方程$27x \equiv 12(mod\ 15)$
	\end{Exercise}
	\jd{
	gcd(27,15)=3，所以同余方程共有3个解，同余方程$9x\equiv 4 (mod\ 5)$的一个特解是x=1,所以原方程全部解为$x\equiv 1+\frac{15}{3}t(mod\ 15),t\in {0,1,2}$，求得其解为1，6，11.
	}
	
	\begin{Exercise}
		求解一次同余方程$24x \equiv 6(mod\ 81)$
	\end{Exercise}
	\jd{
		gcd(24,81)=3，所以同余方程共有3个解，同余方程$8x\equiv 2 (mod\ 27)$的一个特解是x=7,所以原方程全部解为$x\equiv 7+\frac{81}{3}t (mod\ 81),t\in {0,1,2}$，求得其解为7,34,61.
	}

	\begin{Exercise}
		求解一次同余方程$91x \equiv 26(mod\ 169)$
	\end{Exercise}
	\jd{
		gcd(91,169)=13，并且$13 \mid 26$,所以同余方程共有13个解，同余方程$7x\equiv 2 (mod\ 13)$的一个特解是x=4(可以通过遍历的方法求得),所以原方程全部解为$x\equiv 4+\frac{169}{13}t (mod\ 169),t\in {0,1,2,3,4,5,6,7,8,9,10,11,12}$，求得其解为4,17,30,43,56,69,82,95,108,121,134,147,160.
	}

%	\begin{Exercise}
%		求解一次同余方程$71x \equiv 32(mod\ 3441)$ %这道题要算欧拉函数
%	\end{Exercise}
%	\jd{
%		gcd(71,3441)=1，所以同余方程有唯一解，$x\equiv 32 \times 71^{\varphi(3441)-1} (mod\ 3441),\varphi(3441)=2160 \Rightarrow x \equiv 2084(mod\ 3441)
%	}

	\begin{Exercise}
		确定以下同余式不同解的个数，无须求出具体解。
		\begin{enumerate}
			\item $72x \equiv 47(mod\ 200)$
			\item $4183x \equiv 5781(mod\ 15087)$
			\item $1537x \equiv 2863(mod\ 6731)$
		\end{enumerate}
	\end{Exercise}
	\jd{
		gcd(72,200)=8,但是$8 \nmid 47$,所以第一个方程无解。gcd(4183,15087)=47，且$47 \mid 5781$，故第二方程有解，且解的个数为47.gcd(1537,6731)=53,但是$53 \nmid 2863$，故此方程无解。
	}

	\begin{Exercise}
		求解同余方程组：
		$
		\begin{cases}
			x\equiv 9(mod\ 12)\\
			x \equiv 6(mod\ 25)\\	
		\end{cases}
		$
	\end{Exercise}
	\jd{
	gcd(12,25)=1,利用中国剩余定理，唯一解为$x \equiv 25\times 1 \times 9+12\times 23 \times 6 (mod\ 12\times 25) \equiv 1881 \equiv 81(mod\ 300) $
	}

	\begin{Exercise}
		求解同余方程组：
		$
		\begin{cases}
		x\equiv 5(mod\ 7)\\
		x \equiv 12(mod\ 15)\\
		x \equiv 18(mod\ 22)\\	
		\end{cases}
		$
	\end{Exercise}
	\jd{
		$gcd(7,15)=1,gcd(15,22)=1,gcd(7,22)=1$，可以看出以上方程组的模两两互素，根据中国剩余定理，我们有:\par
		$x \equiv 5(mod\ 7),m=7\times 15 \times 22=2310$\\
		$M_1 = 15 \times 22 = 330, M_1' = 1 (mod\ 7)$\\
		$M_2=7*22=154,M_2'=4(mod\ 15)$\\
		$M_3=7*15=105,M_3'=13(mod\ 22)$\\
		$x=M_ 1 M_1' b_1+M_2 M_2' b_2+M_3 M_3' b_3=15\times 1 \times 5+154 \times 4 \times 12+105 \times 13 \times 18 (mod\ 2310) \equiv 1272 (mod\ 2310)$
		
%		%利用sagemath验证结果
%		print "M_1=",15*22,"M_1'=",(15*22).inverse_mod(7)
%		print "M_2=",7*22,"M_2'=",(7*22).inverse_mod(15)
%		print "M_3=",15*7,"M_3'=",(15*7).inverse_mod(22)
%		a=15*22*(15*22).inverse_mod(7)*5+7*22*(7*22).inverse_mod(15)*12+15*7*(15*7).inverse_mod(22)*18
%		b=mod(a,7*15*22)
%		print mod(a,7*15*22)
%		print "idea:5",mod(b,7)
%		print "idea:12",mod(b,15)
%		print "idea:18",mod(b,22)
	}
	\begin{Exercise}
		求解同余方程组：
		$
		\begin{cases}
		x\equiv 5(mod\ 9)\\
		3x \equiv 12(mod\ 5)\\
		4x \equiv 18(mod\ 7)\\	
		\end{cases}
		$
	\end{Exercise}
	\jd{
		先看$3x \equiv 12(mod\ 5)$的解，由于$gcd(3,5)=1$，所以$x\equiv 12 \times 3^{\varphi(5)-1} \equiv 12 \times 3^3 \equiv 324 \equiv 4 (mod\ 5)$\par
		再看$4x \equiv 18(mod\ 7)$的解，由于$gcd(4,7)=1$，所以$x\equiv 4 \times 18^{\varphi(7)-1} \equiv 4 \times 18^5 \equiv 1 (mod\ 5)$\par
		也可以直接化简为以下方程组。\par
		方程组等价于：\par
		$
		\begin{cases}
		x\equiv 5(mod\ 9)\\
		x \equiv 4(mod\ 5)\\
		x \equiv 1(mod\ 7)\\	
		\end{cases}
		$
		\par
		由于9,5,7两两互素，根据中国剩余定理计算可得x=239.
%		%用sagemath求解
%		print crt(5,4,9,5)
%		print crt(23,1,45,7)
%		print "idea 5:",mod(113,9)
%		print "idea 3:",mod(113,5)
%		print "idea 1:",mod(113,7)
	}

	\begin{Exercise}
		有总数不满50人的一队士兵，一至三报数，最后一人报一，一至五报数，最后一人报二，一至七报数，最后一人报二，这支队伍共有士兵多少人。
	\end{Exercise}
	\jd{
		根据题意列出方程：\par
		$
		\begin{cases}
		x\equiv 1(mod\ 3)\\
		x \equiv 2(mod\ 5)\\
		x \equiv 2(mod\ 7)\\	
		\end{cases}
		$
		\par
		3,5,7两两互素，根据中国剩余定理，$m=3 \times 5\times 7=105,M_1=35,M_1'=2,M_2=21,M_2'=1,M_3=15,M_3'=1,x\equiv 35\times 2\times 1+ 21\times 1 \times 2 +15 \times 1 \times 2 \equiv 142 \equiv 37 (mod\ 105)$
		%sagemath 验证
%		print "idea 1:",mod(37,3)
%		print "idea 2:",mod(37,5)
%		print "idea 2:",mod(37,7)
		%结果
%		sage: print "idea 1:",mod(37,3)
%		....: print "idea 2:",mod(37,5)
%		....: print "idea 2:",mod(37,7)
%		....:
%		idea 1: 1
%		idea 2: 2
%		idea 2: 2
%		sage:
		
	}

\chapter{二次剩余}
	\begin{Exercise}
		求模23的二次剩余和非二次剩余
	\end{Exercise}
	\jd{
		23的一个完全剩余系为{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23}，依次计算$i^2 (mod\ 23)$，计算结果组成的集合就是模23二次剩余组成的集合，完全剩余系中不包含在此集合中的元素就是非二次剩余。\par
		$
				1 ^2= 1 (mod 23),2 ^2= 4 (mod 23),3 ^2= 9 (mod 23),4 ^2= 16 (mod 23)\\
				5 ^2= 2 (mod 23),6 ^2= 13 (mod 23),7 ^2= 3 (mod 23),8 ^2= 18 (mod 23)\\
				9 ^2= 12 (mod 23),10 ^2= 8 (mod 23),11 ^2= 6 (mod 23),12 ^2= 6 (mod 23)\\
				13 ^2= 8 (mod 23),14 ^2= 12 (mod 23),15 ^2= 18 (mod 23),16 ^2= 3 (mod 23)\\
				17 ^2= 13 (mod 23),18 ^2= 2 (mod 23),19 ^2= 16 (mod 23),20 ^2= 9 (mod 23)\\
				21 ^2= 4 (mod 23),22 ^2= 1 (mod 23),23 ^2= 0 (mod 23)\\
			$
		二次剩余为0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18\par
		非二次剩余5，7，10，11，14，15，17，19，20，21，22		
}
		%sagemath函数求解二次剩余的过程，也可以直接使用quadratic_residues(23) 计算模23的所有二次剩余
%		sage: for i in range(1,24):
%		....:     print i,"^2=",mod(i^2,23),"(mod 23)"
%		....:
%		1 ^2= 1 (mod 23)
%		2 ^2= 4 (mod 23)
%		3 ^2= 9 (mod 23)
%		4 ^2= 16 (mod 23)
%		5 ^2= 2 (mod 23)
%		6 ^2= 13 (mod 23)
%		7 ^2= 3 (mod 23)
%		8 ^2= 18 (mod 23)
%		9 ^2= 12 (mod 23)
%		10 ^2= 8 (mod 23)
%		11 ^2= 6 (mod 23)
%		12 ^2= 6 (mod 23)
%		13 ^2= 8 (mod 23)
%		14 ^2= 12 (mod 23)
%		15 ^2= 18 (mod 23)
%		16 ^2= 3 (mod 23)
%		17 ^2= 13 (mod 23)
%		18 ^2= 2 (mod 23)
%		19 ^2= 16 (mod 23)
%		20 ^2= 9 (mod 23)
%		21 ^2= 4 (mod 23)
%		22 ^2= 1 (mod 23)
%		23 ^2= 0 (mod 23)
%		sage:
%		
	

	\begin{Exercise}
		求满足方程$E:y^2 \equiv x^2-2x+1 (mod\ 7)$的所有点。
	\end{Exercise}
	\jd{
		首先观察方程的左边是$y^2 (mod\ 7)$的形式，其最终结果是模7的二次剩余，我们计算模7的二次剩余，可知为：0，1，2，4。\par
		$1 ^2= 1 (mod 7),
		2 ^2= 4 (mod 7),
		3 ^2= 2 (mod 7),
		4 ^2= 2 (mod 7),
		5 ^2= 4 (mod 7),
		6 ^2= 1 (mod 7),
		7 ^2= 0 (mod 7)$\par
		$(7k)^2 \equiv 0(mod\ 7),(7k+1 or 6)^2 \equiv 1(mod\ 7),(7k+3 or 4)^2 \equiv 2(mod\ 7),(7k+2 or 5)^2 \equiv 4(mod\ 7)$
		以上方程等价于：\\
		\vspace{1cm} $x^2-2x+1 \equiv 0(mod\ 7)$\ or\ $x^2-2x+1 \equiv 1(mod\ 7)$\ or\ $x^2-2x+1 \equiv 2(mod\ 7)$\ or\ $x^2-2x+1 \equiv 4(mod\ 7)$,对这四个同余式进一步变形，得\par
		\vspace{1cm} $(x-1)^2 \equiv 0(mod\ 7)$\ or\ $(x-1)^2 \equiv 1(mod\ 7)$\ or\ $(x-1)^2 \equiv 2(mod\ 7)$\ or\ $(x-1)^2 \equiv 4(mod\ 7)$,根据模7的二次剩余，进一步知道：\par
		\vspace{1cm}$x \equiv 1(mod\ 7),x \equiv 9(mod\ 7),x \equiv 4(mod\ 7),x \equiv 6(mod\ 7)$\par
		所以满足以上方程的点为(0,1)(1,9)(6,9)(3,4)(4,4)(2,6)(5,6)只要对应的y和x于这些点同余就满足方程。
		}
	
	\begin{Exercise}
		利用欧拉判别条件判断2是否是29的二次剩余。
	\end{Exercise}
	\jd{
		29是奇素数，gcd(2,29)=1，根据欧拉判别条件$a^{\frac{p-1}{2}} = 2^{\frac{29-1}{2}} =2^14 =16384 \equiv -1(mod\ 29)$,所以2不是29的二次剩余。
	}

	\begin{Exercise}
		利用勒让德符号判断2是否是73的二次剩余。
	\end{Exercise}
	\jd{73为奇素数，根据书中定理我们有\par
		
		$
		(\frac{2}{73})= 
		\begin{cases}
			1,if\ p \equiv \pm 1(mod\ 8)\\
			-1,if\ p \equiv \pm 3(mod\ 8)\\
		\end{cases}
		$，
		
		
		$\because 73(mod\ 8)\equiv 1,\therefore (\frac{2}{73})=1 $,2是73的二次剩余。
	}

	\begin{Exercise}
		计算勒让德符号$(\frac{17}{37})$.
	\end{Exercise}

	\begin{Exercise}
		计算勒让德符号$(\frac{37}{25411})$(备注：25411为素数)
	\end{Exercise}
	\jd{
		$gcd(37,25411)=1$\\
		根据二次互反定律，我们有：\\
		$\left( \frac{37}{25411} \right) =(-1)^{\frac{37-1}{2} \frac{25411-1}{2}} (\frac{25411}{37})=(\frac{29}{37})=(-1)^{\frac{29-1}{2} \frac{37-1}{2}} (\frac{37}{29})=(\frac{8}{29})$,然后可以根据二次剩余的定义，知$(\frac{8}{29})=8^{\frac{29-1}{2}} (mod\ 29) \equiv 28 \equiv -1(mod\ 29)$
	}

\chapter{原根与指数}

	\begin{Exercise}
		34对模37的次数是多少？
	\end{Exercise}
	\jd{
		解法一：可以按照定义去求，遍历一个完全系：
		$34^ 0 = 1
		34^ 1 = 34,
		34^ 2 = 9,
		34^ 3 = 10,
		34^ 4 = 7,
		34^ 5 = 16,
		34^ 6 = 26,
		34^ 7 = 33,
		34^ 8 = 12,
		\underline{34^ 9 = 1},
		34^ {10} = 34,
		34^ {11} = 9,
		34^ {12} = 10,
		34^ {13} = 7,
		34^ {14} = 16,
		34^ {15} = 26,
		34^ {16} = 33,
		34^ {17} = 12,
		\underline{34^ {18} = 1},
		34^ {19} = 34,
		34^ {20} = 9,
		34^ {21} = 10,
		34^ {22} = 7,
		34^ {23} = 16,
		34^ {24} = 26,
		34^ {25} = 33,
		34^ {26} = 12,
		\underline{34^ {27} = 1},
		34^ {28} = 34,
		34^ {29} = 9,
		34^ {30} = 10,
		34^ {31} = 7,
		34^ {32} = 16,
		34^ {33} = 26,
		34^ {34} = 33,
		34^ {35} = 12,
		34^ {36} = 1$\par
		由计算结果可知34对模37的次数为9.
%		for i in range(37):
%		   print "34^",i,"=",mod(34^i,37)
		
		解法二：\par
%		sage: euler_phi(37)
%		36
%		sage: 36.divisors()
%		[1, 2, 3, 4, 6, 9, 12, 18, 36]
%		sage:
		可以证明，$ord_m(a) \mid \varphi(m)$，所以，37的欧拉函数是36，6的所有因子是1, 2, 3, 4, 6, 9, 12, 18, 36，依次计算$a^l (mod\ 37),l \in {1, 2, 3, 4, 6, 9, 12, 18, 36}$,结果为1的l最小取值为次数。
	}
	
	\begin{Exercise}
		判断47，55，59的原根是否存在。若存在，求出其所有原根。
	\end{Exercise}
	\jd{
		47是奇素数，根据定理，我们知道47的原根存在。\par
		55的标准分解式$5 \times 11$，根据定理其不是$2,4,p^l,2p^l$的形式，故55没有原根。\par
		59是奇素数，根据定理，我们知道59的原根存在。\par
	}

	\begin{Exercise}
		求47所有原根。
	\end{Exercise}
	\jd{
		47是奇素数，根据定理，我们知道47的原根存在。\par
		$\varphi(47)=46$,46的标准分解式为$2 \times 23$,46互素的因子g为3，5，7，9，$\ldots$，计算$g^{23},g^2$：\par
		$3^{23} \equiv 1,3 ^2\equiv 9$,3不是原根\par
		$4 ^{23}\equiv 1,4 ^2\equiv 16$,4不是原根\par
		$5 ^{23}\equiv 46,5 ^2\equiv 25$,5是原根\par
		$5^l$，l遍历46的缩系，\{ 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45 \}，得到所有原根为\{ 5, 10, 11, 13, 15, 19, 20, 22, 23, 26, 29, 30, 31, 33, 35, 38, 39, 40, 41, 43, 44, 45 \}.
		
%#caculate reduced residue system
%reducedrs=[]
%for i in range(1,46):
%if gcd(46,i)==1:
%reducedrs.append(i)
%print reducedrs
%#caculate all primitive roots
%priroot=[]
%for i in reducedrs:
%priroot.append(mod(5^i,47))
%priroot.sort()
%print priroot
%#verify all primitive root
%for i in priroot:
%print "the euler function of 47 is 46,the order of ",i," module 47 is ",Mod(5,47).multiplicative_order(),"."		
	}

\chapter{编程练习}
	\begin{Exercise}
		编写程序计算两个大数(任意精度)的四则运算($+,-,\times$,$\div$ ),模运算。注：32位系统，C语言长整型为$2^{32}-1=4294967295$，64位系统是$2^{64}-1$.
	\end{Exercise}
	
	\begin{Exercise}
		编程实现埃拉托色尼(Eratosthenes，古希腊数学家)筛选法寻找素数，按一定的步长计算一系列不同范围内的素数(500$\sim$1000000)，并记录算法所用时间，并画出不同范围时算法所用时间的变化曲线。注：不同范围搜寻的时间可以以一定的格式写到文本文件中，比如34,500 <换行>，每一个搜寻范围形成这样一行数据，然后将这个数据文件导入excel，用excel生成图形。
	\end{Exercise}

	\begin{Exercise}
		利用C语言已有的运算，编写程序计算两个数的最大公约数。
	\end{Exercise}

	\begin{Exercise}
		利用GMP实现任意精度的两个数的最大公约数的求解。
	\end{Exercise}
	
	\begin{Exercise}
		编程判断两个数是否互素。
	\end{Exercise}
	
	\begin{Exercise}
		1858年法国密码学家维吉尼亚提出一种以移位替换为基础的周期替换密码,c称为Vigenère Cipher，这种密码是多表替换密码的一种。令英文字母a,b,…,z对应于从0到25的整数，明文是n个字母组成的字符串，即 $M=m_1m_2m_3m_4 \ldots m_n$，密钥也是一个字符串$K=k_1 k_2 \ldots k_q$，通常短一些，加密后的密文$C=c_1 c_2 \ldots c_n$，$c_i =m_i + k_i \ (mod\ 26)$，如果$q<n$，将密钥进行周期性延展,解密为$m_i = c_i - k_i (mod\ 26)$。\par
		编写程序实现Vigenère加解密。
	\end{Exercise}
	
	\begin{Exercise}
		编写程序计算22345680的标准分解式。
	\end{Exercise}

	

	\begin{Exercise}
		编写程序实现求解一个整数的标准分解，同时在分解完成后，输出分解所用的时长。
	\end{Exercise}

	\begin{Exercise}
		编写程序实现输入范围的素数生成，并且明确程序有能力求解的范围。
	\end{Exercise}
	
	\begin{Exercise}
		编程判断同余方程$ax \equiv b(mod\ m)$是否有解，如果有解，求出所有的解。
	\end{Exercise}
	
	\begin{Exercise}
		编写程序实现利用中国剩余定理求解同余方程组。
	\end{Exercise}
	
\end{document}